package 二叉树;

import java.util.*;

public class 二叉树的迭代遍历 {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Soultion{
        //前序遍历顺序：中左右 ，入栈顺序：中右左
         public List<Integer> preorderTraversal(TreeNode root){
             ArrayList<Integer> result  = new ArrayList<>();
             if (root == null){
                 return  result;
             }
             Stack<TreeNode> stack = new Stack<>();
             stack.push(root);
             while (!stack.isEmpty()){
                 TreeNode node = stack.pop();
                 result.add(node.val);
                 if (node.right!=null){
                     stack.push(node.right);
                 }
                 if (node.left!=null){
                     stack.push(node.left);
                 }
             }
             return result;
         }

         //中序遍历
         public List<Integer> inorderTraversal(TreeNode root){
             ArrayList<Integer> result = new ArrayList<>();
             if (root == null){
                 return result;
             }
             Stack<TreeNode> stack = new Stack<>();
             TreeNode curr = root;
             while(!stack.isEmpty()||curr != null){
                if (curr!=null){
                    stack.push(curr);
                    curr = curr.left;
                }else {
                    curr = stack.pop();
                    result.add(curr.val);
                    curr = curr.right;
                }
             }

              return result;
         }

         //后序遍历 要翻转结果
         public List<Integer> postorderTraversal(TreeNode root){
             ArrayList<Integer> result  = new ArrayList<>();
             if (root == null){
                 return  result;
             }
             Stack<TreeNode> stack = new Stack<>();
             stack.push(root);
             while (!stack.isEmpty()){
                 TreeNode node = stack.pop();
                 result.add(node.val);
                 if (node.left!=null){
                     stack.push(node.left);
                 }
                 if (node.right!=null){
                     stack.push(node.right);
                 }
             }
             Collections.reverse(result);
             return result;

    }
    }
}
